package m202401.d07;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/1/7 10:24
 */
//86. 分隔链表
public class Q86 {
    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(-1);
        ListNode pl = left;
        ListNode right = new ListNode(-1);
        ListNode pr = right;
        ListNode p = head;
        while (p != null) {
            ListNode temp = p.next;
            p.next = null;
            if (p.val < x) {
                pl.next = p;
                pl = pl.next;
            } else {
                pr.next = p;
                pr = pr.next;
            }
            p = temp;
        }
        pl.next = right.next;
        return left.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
